package com.shiguiwu.springmybatis.algorithm.sort;

import java.util.Arrays;

/**
 * @description: 希尔排序
 * 希尔排序又叫缩小增量排序法
 * 其实就是一个改进的插入排序,
 * @author: stone
 * @date: Created by 2021/3/17 20:16
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class ShellSort extends AbstractSort implements Sort {

    public static void main1(String[] args) {
        int[] init = SortTests.init(9);
        System.out.println(Arrays.toString(init));
        Sort sort = new ShellSort(init);
        sort.sort();
        System.out.println(Arrays.toString(init));

    }
    public ShellSort(int[] array) {
        super(array);
    }

    /**
     * 这里我们用的是shell位移法。。。。。。。。。
     */
    @Override
    public void sort() {
        int len = array.length;
        //分组，例如：10位数数组 10/2 =5 组 5/2 =2 2/2 = 0
        for (int gap = len / 2; gap > 0; gap /= 2) {
            //从gap位置开始，逐个对其所在的组进行插入排序
            for (int i = gap; i < len; i++) {
                //待插入的元素
                int insertVal = array[i];
                //寻找的位置
                int indexVal = i;
                while (indexVal-gap >= 0 && insertVal < array[indexVal - gap]) {
                    //后移
                    array[indexVal] = array[indexVal - gap];
                    indexVal -= gap;
                }
                array[indexVal] = insertVal;
            }
        }
    }
}
